package com.ly.algorithm.leetcode.dp;

/**
 * @Classname Problem91
 * @Description
 *
 * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
 *
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 给定一个只包含数字的非空字符串，请计算解码方法的总数。
 *
 * 题目数据保证答案肯定是一个 32 位的整数。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "12"
 * 输出：2
 * 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
 * 示例 2：
 *
 * 输入：s = "226"
 * 输出：3
 * 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
 * 示例 3：
 *
 * 输入：s = "0"
 * 输出：0
 * 示例 4：
 *
 * 输入：s = "1"
 * 输出：1
 * 示例 5：
 *
 * 输入：s = "2"
 * 输出：1
 *
 * @Date 2020/12/23 18:01
 * @Author 冷心影翼
 */
public class Problem91 {

	public static void main(String[] args) {
		Solution91 solution91 = new Solution91();
		System.out.println(solution91.numDecodings("226"));
	}

}


class Solution91 {

	public int numDecodings(String s) {
		int n = s.length();
		int[] dp = new int[n+1];
		if(s.length()<=0 || s.charAt(0) == '0')
			return 0;
		dp[0] = 1;
		dp[1] = 1;
		for(int i=2;i<n+1;i++) {
			if(s.charAt(i-1) == '0' ) {
				if(s.charAt(i-2) == '1' || s.charAt(i-2) == '2') {
					dp[i] = dp[i-2];
				}else {
					return 0;
				}
			}else {
				if (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))
					dp[i] = dp[i - 1] + dp[i - 2];
				else {
					dp[i] = dp[i - 1];
				}
			}
		}
		return dp[n];
	}
}
